Trong giai đoạn từ năm 1852 – 1856, Livingstone, trong nỗ lực khám phá châu Phi, đã trở thành người châu Âu đầu tiên nhìn thấy thác Mosi-oa-Tunya ("khói đang gầm thét"), ông chọn cho nó một tên mới, Thác Victoria, theo tên của Nữ hoàng Victoria. Về sau ông viết, "Cảnh quan quá tuyệt vời đến nỗi các thiên sứ đang bay chắc cũng phải ngắm nhìn."[10]

Livingstone cũng là người phương Tây đầu tiên thực hiện cuộc hành trình băng ngang lục địa Phi châu, từ Luanda (nay là thủ đô của Angola) bên bờ Đại Tây Dương tới Quelimane cạnh Ấn Độ Dương gần cửa sông Zambezi trong những năm 1854-56.[5] Mặc dù đã có nhiều đoàn thám hiểm đến từ châu Âu, nhất là những người Bồ Đào Nha, chưa có người Âu nào từng băng qua trung và nam châu Phi kể từ vĩ độ này bởi vì nỗi e sợ đối với bệnh sốt rét, bệnh lỵ, và bệnh trùng mũi khoan châu Phi (bệnh buồn ngủ) đang lan rộng trong vùng, điều này cũng khiến họ không thể sử dụng sức kéo của bò và ngựa cũng như gặp phải sự chống đối của những bộ tộc hùng mạnh như Lozi và Lunda của Mwata Kazembe. Tuy nhiên, Livingstone có những lợi thế của riêng mình, ông tổ chức những chuyến thám hiểm gọn nhẹ, lại có khả năng thuyết phục các tù trưởng rằng ông không phải là mối đe dọa đối với họ, không giống những đoàn thám hiểm khác có nhiều lính vũ trang hộ tống cùng hàng chục phu khuân vác, trông giống như những cuộc tấn công của quân đội hoặc những vụ bố ráp của những nhóm buôn nô lệ. Với một đoàn tùy tùng chỉ có vài người giúp việc và một ít người khuân vác, Livingstone và đoàn thám hiểm của ông trong suốt chuyến đi phải trao đổi với người bản địa để có những vật cần dùng, ông chỉ đem theo mình hai khẩu súng để tự vệ. Livingstone thường truyền bá thông điệp phúc âm nhưng không buộc người khác phải lắng nghe; ông hiểu tập quán của những tù trưởng và thương thảo để được phép băng qua lãnh thổ của họ, thường khi ông được đón tiếp tử tế và nhận được sự giúp đỡ từ họ, ngay cả từ Mwata Kazembe.

Mục tiêu của những chuyến thám hiểm là mở các tuyến đường, cũng như khảo sát châu lục này. Những quan tâm khác của Livingstone là mở rộng giao thương và thiết lập các cơ sở truyền giáo tại Trung Phi. Phương châm của Livingstone, được ghi dưới chân bức tượng của ông đặt tại Thác Victoria, là "Cơ Đốc giáo, Giao thương, và Khai hóa". Lý do khiến Livingstone ủng hộ ba nguyên tắc trên là vì ông tin rằng chúng sẽ có thể thay thế nạn buôn bán nô lệ lúc ấy đang tràn lan ở châu Phi, cũng như cho người Phi phẩm giá khi tiếp xúc với người Âu. Hủy bỏ chế độ nô lệ ở châu Phi luôn là mục tiêu quan trọng trong cuộc đời Livingstone.[11] Khi ấy ông tin rằng giải pháp giúp hoàn thành các mục tiêu trên là tổ chức cuộc hành trình thám hiểm dòng sông Zambezi để đi sâu vào nội địa.[12] Livingstone trở về Anh Quốc để tìm kiếm hậu thuẫn cho ý tưởng này, và xuất bản một cuốn sách viết về những chuyến đi của ông, tác phẩm này đã mang đến cho ông thanh danh của nhà thám hiểm hàng đầu trong thời đại ông.

Tin rằng mình nhận lãnh ơn gọi để thực hiện các chuyến thám hiểm chứ không phải để tham gia vào công cuộc truyền giáo, cùng lúc là những đáp ứng thuận lợi từ nước Anh đề nghị hỗ trợ cho các chuyến thám hiểm kế tiếp, là những nhân tố dẫn đến quyết định của Livingstone từ nhiệm khỏi Hội Truyền giáo Luân Đôn để tập trung vào mục tiêu khám phá châu Phi. Nhờ sự vận động của chủ tịch Hội Địa lý Hoàng gia, Livingstone được bổ nhiệm là Cố vấn của Nữ hoàng về Bờ biển phía Đông của châu Phi[5]

Thám hiểm Sông Zambezi

Livingstone trở lại Phi châu trong cương vị người đứng đầu đề án "Thám hiểm sông Zambezi" được chính phủ Anh tài trợ nhằm khảo sát tài nguyên thiên nhiên trong vùng đông nam châu Phi. Khi vượt qua thác Cabora Bassa, Livingstone mới nhận ra rằng lưu thông trên Sông Zambezi là hoàn toàn bất khả. Một chuỗi thác lớn đã khiến cuộc hành trình của Livingstone thất bại ngay trong giai đoạn đầu.[12]

Cuộc thám hiểm sông Zambezi khởi sự từ tháng 3 năm 1858 và kéo dài đến giữa năm 1864. Các thành viên trong đoàn thám hiểm cho rằng Livingstone là một nhà lãnh đạo thiếu kinh nghiệm và gặp khó khăn trong kỹ năng điều hành một đề án quy mô lớn. Ông cũng bị chỉ trích là không chịu bàn bạc công khai, tự mãn, và thường rầu rĩ.[13] Thomas Baines, một họa sĩ trong đoàn thám hiểm, bị sa thải vì những nghi ngờ về trộm cắp dù Baines bác bỏ cáo buộc này.

Trước tiên, đoàn đến Hồ Malawi trên một chiếc xuồng bốn mái chèo, rồi tiến hành thám hiểm hồ. Đến năm 1862, đoàn quay lại bờ biển đợi chiếc tàu chạy bằng hơi nước được thiết kế đặc biệt để di chuyển trên hồ Malawi. Mary Livingstone đi trên thuyền này. Sau những thất bại của đoàn khi cố thăm dò Sông Ruvuma bởi vì bánh xe guồng của tàu hơi nước bị vướng vào những thi thể trôi sông – nạn nhân của bọn người buôn nô lệ; rồi thì các phụ tá của Livingstone hoặc qua đời hoặc rời bỏ đoàn.[13] Ngày 29 tháng 4 năm 1863, Mary, vợ của Livingstone, qua đời vì bệnh sốt rét, nhưng Livingstone vẫn tiếp tục cuộc hành trình cho đến khi bị buộc phải quay về nước Anh vào năm 1864, khi chính phủ ra lệnh hủy bỏ cuộc thám hiểm bởi vì chi phí gia tăng, và vì không thể tìm ra một thủy lộ đi sâu vào nội địa.

Chuyến thám hiểm sông Zambezi được miêu tả trên báo chí thời ấy như là một thất bại khiến Livingstone gặp nhiều khó khăn trong nỗ lực tìm kiếm hỗ trợ tài chính cho công cuộc khám phá châu Phi. Tuy vậy, các nhà khoa học từng làm việc dưới quyền Livingstone như John Kirk, Charles Meller, và Richard Thornton đã đóng góp những bộ sưu tập dữ liệu lớn về các lĩnh vực như thực vật, sinh thái, địa chất và dân tộc học cho các định chế khoa học tại Anh.

Thượng nguồn sông Nile

Trong khi những nhà thám hiểm như Richard Francis Burton, John Hanning Speke, và Samuel Baker cho rằng Hồ Albert hoặc Hồ Victoria là nguồn của sông Nile, Livingstone tin rằng thượng nguồn sông Nile nằm sâu ở phía Nam.[14] Ông tập hợp một nhóm gồm những nô lệ được tự do, thổ dân quần đảo Comoros, mười hai người Sepoys, và hai phụ tá trung thành, Chuma và Susi, cùng đi với ông từ chuyến thám hiểm trước.

Khởi hành từ cửa sông Ruvuma, nhưng những người trong đoàn dần dần từ bỏ Livingstone. Các thổ dân Comoros trở về từ Zanzibar báo cho giới thẩm quyền rằng Livingstone đã chết. Ngày 6 tháng 8, ông tới Hồ Malawi, hầu hết hành trang của ông, kể cả thuốc men, đều bị mất cắp. Livingstone băng qua khu đầm lầy tiến tới Hồ Tanganyika. Do sức khỏe suy giảm, ông nhắn tin về Zazibar yêu cầu gởi vật dụng đến Uiji, rồi ông đi tiếp về hướng Tây. Do sức khỏe kém, ông bị buộc phải đi cùng những tay buôn nô lệ, ngày 8 tháng 10 năm 1867, Livingston đến Hồ Mweru, tiếp tục cuộc hành trình về phía Nam, ông trở thành người Âu đầu tiên nhìn thấy Hồ Bangweulu. Khi tìm thấy Sông Lualaba, ông nhầm tưởng đó là thượng lưu Sông Nile.

Năm 1869, bệnh trở nặng khi Livingstone đang ở trong rừng. Những tay buôn nô lệ người Ả Rập cứu ông bằng cách cho ông thuốc và mang ông đến một trạm tiền phương của người Ả Rập.[15] Tháng Ba năm 1869, với bệnh lao trong người, Livingstone đến Ujiji để tìm lại vật dụng bị đánh cắp. Lại mắc thêm bệnh tả và ung loét nhiệt đới ở chân, ông bị buộc phải nhờ những tay buôn nô lệ đưa ông đến Bambara, rồi bị kẹt lại tại đây vì mùa mưa.[13]

Ngày 15 tháng 7 năm 1871,[16] khi đến thăm thị trấn Nyangwe bên bờ sông Lualaba, Livingstone chứng kiến vụ tàn sát 400 người Phi dưới tay bọn buôn nô lệ.[17] Vụ này khiến ông kinh tởm đến nỗi gần như suy sụp không thể tiếp tục chuyến đi tìm kiếm thượng nguồn sông Nile.[16] Hết mùa mưa, Livingstone đi tiếp quãng đường dài 240 dặm (390 km) từ Nyangwe – ông bị bệnh nặng trong suốt chuyến đi – trở lại Ujiji, một khu định cư của người Ả Rập trên bờ đông hồ Tanganyika. Đó là ngày 23 tháng 10 năm 1871.

Dù nhận định sai về sông Nile, Livingstone đã khám phá nhiều địa điểm như Hồ Ngami, Hồ Malawi, và Hồ Bangweulu, ngoài Thác Victoria đã kể ở trên. Ông thu thập nhiều chi tiết về hồ Tanganyika, hồ Mweru, và địa hình của nhiều dòng sông, đặc biệt ở vùng Zambebi thượng, cùng những khảo sát của ông đã giúp nhận diện những vùng đất rộng lớn trước đây còn để trống trên bản đồ.[18]